package Trie

type Trie struct {
	Value       rune
	End         bool
	FirstChild  *Trie
	NextBrother *Trie
}

/** Initialize your data structure here. */
func Constructor() Trie {
	return Trie{}
}

/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
	l := len(word)
	tail := this
	for i, c := range word {
		if tail.FirstChild == nil {
			tail.FirstChild = &Trie{
				Value: c,
			}
			tail = tail.FirstChild
			if i == l-1 {
				tail.End = true
			}
			continue
		}

		if tail.FirstChild.Value == c {
			tail = tail.FirstChild
			if i == l-1 {
				tail.End = true
			}
			continue
		}

		tail = tail.FirstChild
		for {
			if tail.NextBrother == nil {
				tail.NextBrother = &Trie{
					Value: c,
				}
				tail = tail.NextBrother
				break
			}
			if tail.NextBrother.Value == c {
				tail = tail.NextBrother
				break
			}
			tail = tail.NextBrother
		}
		if i == l-1 {
			tail.End = true
		}
	}

	return
}

/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
	l := len(word)
	tail := this
	for i, c := range word {
		if tail.FirstChild == nil {
			return false
		}
		if tail.FirstChild.Value == c {
			if i == l-1 && tail.FirstChild.End {
				return true
			}
			tail = tail.FirstChild
			continue
		}
		tail = tail.FirstChild
		for {
			if tail.NextBrother == nil {
				return false
			}
			if tail.NextBrother.Value == c {
				if i == l-1 && tail.NextBrother.End {
					return true
				}
				tail = tail.NextBrother
				break
			}
			tail = tail.NextBrother
		}
	}
	return false
}

/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
	l := len(prefix)
	tail := this
	for i, c := range prefix {
		if tail.FirstChild == nil {
			return false
		}
		if tail.FirstChild.Value == c {
			if i == l-1 {
				return true
			}
			tail = tail.FirstChild
			continue
		}

		tail = tail.FirstChild
		for {
			if tail.NextBrother == nil {
				return false
			}
			if tail.NextBrother.Value == c {
				if i == l-1 {
					return true
				}
				tail = tail.NextBrother
				break
			}
			tail = tail.NextBrother
		}
	}
	return false
}

/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */
